---------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------
-- File: priority_queue - priority queue source file.
-- Author: Andy Schneck                         
-- Description: 
--
-- Inputs: data_in:
--	       priority_in:
--	       operation_in:
--	       clk:	
--	       reset:
--
-- Outputs: queue_ready:
--	    empty:
--	    full:
--      data_out:
---------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------
package queue_operations is
	type operation is (enqueue, dequeue, no_op);
end package queue_operations; 

library ieee;
use work.queue_operations.all;
use ieee.std_logic_1164.ALL;
use ieee.std_logic_arith.ALL;
use ieee.std_logic_unsigned.ALL; 

--------------------------------------------
-- entity declaration for the fifo buffer --	   
--------------------------------------------
entity priority_queue is   
port(
		data_in     	:   in std_logic_vector(31 downto 0);	-- input data (16 bits)
		priority_in 	:   in std_logic_vector(3 downto 0);    -- priority (4 bits)
		operation_in	:	in operation;						-- queue operations
		clk	 			: 	in std_logic;						-- clock
		reset			: 	in std_logic;						-- reset switch (active high)
		empty 			: 	out std_logic;						-- empty flag
		full 			: 	out std_logic;						-- full flag
		data_out    	:   out std_logic_vector(31 downto 0)); -- output data (16 bits)
end priority_queue;

----------------------------------------------
-- architecture body for the priority queue --	   
----------------------------------------------
architecture behav of priority_queue is
	type queue is array(integer range 0 to 63) of std_logic_vector(31 downto 0);-- queue array type
    signal queue_array		:   queue;							-- actual 2-D queue array
	type pri is array(integer range 0 to 63) of std_logic_vector(3 downto 0);	-- priority array type
    signal priority_array	:   pri;                    		-- actual 2-D priority array	
	signal temp_full    	:   std_logic := '0';       		-- temp full flag
    signal temp_empty   	:   std_logic := '0';       		-- temp empty flag	
	signal temp_ready   	:   std_logic := '0';       		-- temp ready flag
	signal index     		:   integer range 0 to 63 := 0;		-- queue/priority pointer (index) 
	signal last_enqueue	    :   std_logic := '0';               -- last action flag: enqueue
    signal last_dequeue     :   std_logic := '0';               -- last action flag: dequeue
	signal temp_data		:   std_logic_vector(15 downto 0);
	signal temp_priority    :   std_logic_vector(3 downto 0);
	signal flag		   	    :   integer range -1 to 63 := 0;
	signal location	   	    :   integer range 0 to 63 := 0;
	signal highest			:	std_logic_vector(3 downto 0);
begin  
	
    ---------------------------------------------------------------------------------------
    -- Check/Set full/empty queue process:
    --
    ---------------------------------------------------------------------------------------
	process(reset, clk, operation_in)
	begin
		if(reset = '0') then -- if reset is not selected
			case operation_in is
				-- enqueue case
				when enqueue =>	
					temp_empty <= '0'; -- if enqueue is issued, then the queue is not empty	
					 
					-- if the pointers are equal and the last action was an enqueue, then the queue is full
					if(index = 63 and last_enqueue = '1') then
	                	temp_full <= '1';
		            else
		                temp_full <= '0';
		            end if;
				
			    -- dequeue case
				when dequeue =>
					temp_full <= '0'; -- if dequeue is issued, then the queue is not full
    				  
					-- if the pointers are at 0 and the last action was a dequeue, then the queue is empty
					if(index = 0 and last_dequeue = '1') then
		                temp_empty <= '1';
		            else
		                temp_empty <= '0';
	            	end if;
				
				-- no-op case
				when no_op => 
					-- save state of flags
					temp_empty <= temp_empty;
					temp_full <= temp_full;
					
				-- default case	
				when others =>
				
			end case;
		else -- if reset is selected 
			-- reset empty/full	flags
			temp_full <= '0';
			temp_empty <= '1'; 
		end if;	
	end process;
	
	---------------------------------------------------------------------------------------
    -- Enqueue/Dequeue process:
	--
    ---------------------------------------------------------------------------------------
	process(reset, operation_in)   
		
	begin
		if(reset = '0') then -- if reset is not selected
			case operation_in is 
				--enqueue case
				when enqueue =>	
					if(last_dequeue = '1') then -- if last action was a dequeue, reset the last enqueue flag
                		last_enqueue <= '0';
            		end if;
					
					if(temp_full = '0') then
						last_enqueue <= '1'; -- set the last action flag
						
						priority_array(index) <= priority_in;
						queue_array(index) <= data_in;
						
						if(index = 0) then -- if the queue is empty
							queue_array(index) <= data_in;
							priority_array(index) <= priority_in;		  
						else -- if the queue is not empty  
							flag <= 0;
							for counter in 0 to index loop
								if(priority_in > priority_array(counter)) then 
									location <= counter;
									if(flag > -1) then
										for counter2 in index downto location+1 loop -- shift everything down
											priority_array(counter2) <= priority_array(counter2-1);
											queue_array(counter2) <= queue_array(counter2-1);  
										end loop;
									end if;
									priority_array(location) <= priority_in;
									queue_array(location) <= data_in; 	  
									flag <= -1;	  
								end if;
							end loop;
						end if;
						if (index < 63)then -- keep incrementing while the write enable is selected
                    		index <= index + 1;
                		else
                    		index <= 0; -- reset pointer
                		end if; 
					else
						last_enqueue <= '0';
					end if;
					
				-- dequeue case	
				when dequeue =>
					if(last_enqueue = '1') then -- if last action was an enqueue, reset the last dequeue flag
                		last_dequeue <= '0';
            		end if;
					
					if(temp_empty = '0') then
						last_dequeue <= '1'; -- set the last action flag 

						--pop off the top (highest priority)
						data_out <= queue_array(0);
						
						--shift the array down
						for counter in 0 to index loop
							priority_array(counter) <= priority_array(counter+1);
							queue_array(counter) <= queue_array(counter+1);
						end loop;	
						
						index <= index -1; -- decrement the index
					else
						last_dequeue <= '0';
					end if;
					
				-- no-op case
				when no_op =>  
					-- save state of action flags/index
					last_dequeue <= last_dequeue;
					last_enqueue <= last_enqueue;
					index <= index;
					
				-- default case
				when others =>
				
			end case;
		else -- if reset is selected 
			-- reset flags
			temp_ready <= '1';
			
			-- reset index
			index <= 0;	 
			
			-- flush the queue and priority array
          	for counter in 0 to 63 loop
               queue_array(counter) <= "00000000000000000000000000000000"; -- reset the queue array
			   priority_array(counter) <= "0000"; -- reset the priority array
           	end loop;  
		end if;	
	end process;
		-- set the flags
	full <= temp_full;
	empty <= temp_empty;
end behav;
